/* 
 * This code aims to report dense subgraphs from 
 * a given adjacency list (please read README for its format).
 *
 * If you are interesed in our Bioinformatics paper, please refer:
 *      ----------------------------------------------------
 *      C. Wu, A. Kalyanaraman. 
 *         -"An efficient parallel approach for identifying 
 *           protein families in large-scale metagenomic data sets"
 *           Proc. IEEE/ACM Supercomputing Conference (SC'08),
 *           Austin, TX, November 15-21.
 *      ----------------------------------------------------
 *
 * Author: A.W.@Washington State Univ. 2008.
 * Email: cwu2@eecs.wsu.edu
 * 
 * Any suggestions or comments? email me.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "loadgraph.h"
#include "loadgraph.h"
#include "vidmap.h"
#include "lib.h"
#include "elib.h"

#define MAX_NAME_LEN 200

char gAdjFile[MAX_NAME_LEN];
char **n2gidHash; /* i -> gid */

int gN; /* #valid vertices, it changes */
int gNN; /* number of original lines, it is fixed */
int gC;
int gS;
ulong *gA;
ulong *gB;
ulong gLgPrime;

SGL *gFSgl;
SGL *gSSgl;

/* these global vars should not be shared */
int mfSglCnt;
int fSglCnt;
int sSglCnt;  /* #(second level shingles) */
int msSglCnt; /* upper bound */
struct ufind *uSet;
int *vidmap; /* track position of vertices index in heap (array) */

int main(int argc, char *argv[]){

    int i;
    int singleton;
    SGL *res;

    void init_vars(void);
    void free_vars(void);
    int options_check(int argc, char **argv);
    
    if(options_check(argc, argv) != 4){
        printf("Usage : %s -f {adjlist} -n {#vertice} -s {} -c {}\n", argv[0]);
	    exit(-1);
    }
    
    gNN = gN;
    
    /* alloc mem */
    init_vars();
    init_vidmap(vidmap, gN);
    gLgPrime = large_prime();
    fetch_rands(gA, gB, gC, gLgPrime);
    printf("Initialization succeed...\n");
    

    load_graph(gAdjFile, gN, vidmap); /* gN might be changed, becz of pruning */
    fSglCnt = gN*gC; /* real #sgls */
    printf("#vertices:%d => %d\n",gNN, gN);
    printf("First level shingling succeed...\n");


    /* at most gN*gC*gC/gS */  
    msSglCnt = fSglCnt*gC/gS; /* second sgl depends on first sgl */
    gSSgl = ecalloc(msSglCnt, sizeof *gSSgl);
    /* sSglCnt: #sgls */
    sSglCnt = re_shingle(gFSgl, fSglCnt, gSSgl, msSglCnt);
    printf("Second level shingling succeed...\n");


    /* gFSgl is sorted in re_shingle() */
    for(i=0; i<sSglCnt; i++){
        res = bsearch(&gSSgl[i], gFSgl, fSglCnt, sizeof *gFSgl, node_val_cmp);
        list_union(uSet, res->vids, gS, gSSgl[i].vids, gS);
    }
    /* dump clusters */
    singleton = gS;
    disp_all_clusters(uSet, gNN, &singleton, ".");
    printf("Dumping clusters succeed...\n");


    /* free resources */
    free_vars();
    return EXIT_SUCCESS;
}

void init_vars(void){
    uSet = init_union(gN);

    /* init global vars */
    vidmap = emalloc(gN*(sizeof *vidmap));

    gA = emalloc(gC*(sizeof *gA));
    gB = emalloc(gC*(sizeof *gB));

    mfSglCnt = gN*gC;
    gFSgl = ecalloc(mfSglCnt, sizeof *gFSgl);

    n2gidHash = ecalloc(gN, sizeof(*n2gidHash));
}

void free_vars(void){
    /* free resource */
    free(vidmap);
    free(gA);
    free(gB);
    free_union(uSet);
    free_sgl(gFSgl, fSglCnt);
    free_sgl(gSSgl, msSglCnt);
    free_hash();
    free_gid_hash(n2gidHash, gNN);
}

int options_check(int argc, char **argv){
	int option;
	int cnt = 0;
	
	while(-1 != (option = getopt(argc, argv, "f:n:s:c:"))){
		switch (option){
		    case '?':
                printf("Usage : %s -f {adjlist} -n {#vertice} -s {} -c {}\n", argv[0]);
			    exit(-1);
		    case 'f':
			    strncpy(gAdjFile, optarg, MAX_NAME_LEN);
			    cnt++;
			    break;
		    case 'n':
			    gN = atoi(optarg);
			    cnt++;
			    break;
		    case 's':
                gS = atoi(optarg);
			    cnt++;
			    break;
		    case 'c':
                gC = atoi(optarg);
			    cnt++;
			    break;
		}
	}
	return cnt;
}
